package leetcode_1_200;

public class LeeCode_198 {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 1, 1, 2}));
        System.out.println(rob(new int[]{1,2,3,1}));
        System.out.println(rob(new int[]{2,7,9,3,1}));
    }
    private static class Node{
        private int val;
        private boolean get;
    }
    private static int rob2(int[] nums) {
        int f0 = 0, f1 = 0;
        for (int num : nums) {
            int newF = Math.max(f0 + num, f1);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }
    private static int rob(int[] nums) {
        int n = nums.length;
        Node[] dp = new Node[n];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new Node();
        }
        dp[0].val = nums[0];
        dp[0].get = true;
        if (n > 1){
            if (nums[1] > nums[0]){
                dp[1].val = nums[1];
                dp[1].get = true;
            }else {
                dp[1].val = nums[0];
                dp[1].get = false;
            }
        }
        for (int i = 2; i < nums.length; i++) {
            if (!dp[i - 1].get){
                dp[i].val = dp[i - 1].val + nums[i];
                dp[i].get = true;
            }else {
                int n1 = dp[i - 2].val + nums[i];
                int n2 = dp[i - 1].val;
                if (n1 > n2){
                    dp[i].val = n1;
                    dp[i].get = true;
                }else {
                    dp[i].val = n2;
                }
            }
        }
        return dp[n - 1].val;
    }
}
